class Solution(object):
    def countSteppingNumbers(self, low, high):
        """
        :type low: int
        :type high: int
        :rtype: List[int]
        """
        out = []

        def search(i, num, k):
            if k < 0:
                if num >= low:
                    out.append(num)
            else:
                if i == 0:
                    now_value = num + 10 ** k
                    if now_value <= high:
                        search(1, now_value, k - 1)
                else:
                    if i == 9:
                        now_value = num + 8 * 10 ** k
                        if now_value <= high:
                            search(8, now_value, k - 1)
                    else:
                        now_value = num + (i - 1) * 10 ** k
                        if now_value <= high:
                            search(i - 1, now_value, k - 1)
                        now_value = num + (i + 1) * 10 ** k
                        if now_value <= high:
                            search(i + 1, now_value, k - 1)

        for i in range(10):
            if low <= i <= high:
                out.append(i)
        for i in range(1, 10):
            base = 10 ** i
            for j in range(1, 10):
                now_base = j * base
                if now_base >= low or (j + 1) * base >= low:
                    if now_base <= high:
                        search(j, now_base, i - 1)
                    else:
                        if now_base > high:
                            return out


data = Solution()
low = 0
high = 21
print(data.countSteppingNumbers(low, high))
